// ============================================================================
//   Copyright 2006-2009 Daniel W. Dyer
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.
// ============================================================================
package org.uncommons.watchmaker.examples.geneticprogramming;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import org.uncommons.watchmaker.framework.operators.AbstractCrossover;

/**
 * Cross-over operator for the trees of {@link Node}s used in the genetic
 * programming example application.
 * @author Daniel Dyer
 */
public class TreeCrossover extends AbstractCrossover<Node>
{
    /**
     * Creates a single-point cross-over operator.
     */
    public TreeCrossover()
    {
        super(1);
    }


    /**
     * Swaps randomly selected sub-trees between the two parents.
     * @param parent1 The first parent.
     * @param parent2 The second parent.
     * @param numberOfCrossoverPoints The number of cross-overs to perform.
     * @param rng A source of randomness.
     * @return A list of two offspring, generated by swapping sub-trees
     * between the two parents.
     */
    @Override
    protected List<Node> mate(Node parent1,
                              Node parent2,
                              int numberOfCrossoverPoints,
                              Random rng)
    {
        List<Node> offspring = new ArrayList<Node>(2);
        Node offspring1 = parent1;
        Node offspring2 = parent2;

        for (int i = 0; i < numberOfCrossoverPoints; i++)
        {
            int crossoverPoint1 = rng.nextInt(parent1.countNodes());
            Node subTree1 = parent1.getNode(crossoverPoint1);
            int crossoverPoint2 = rng.nextInt(parent2.countNodes());
            Node subTree2 = parent2.getNode(crossoverPoint2);
            offspring1 = parent1.replaceNode(crossoverPoint1, subTree2);
            offspring2 = parent2.replaceNode(crossoverPoint2, subTree1);
        }

        offspring.add(offspring1);
        offspring.add(offspring2);
        return offspring;
    }
}
